package top.fengleifeng.question;

/**
 * @program: leetcode-test
 * @description: 给定一个二叉树，我们在树的节点上安装摄像头。
 * 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
 * 计算监控树的所有节点所需的最小摄像头数量。
 * 示例 1：
 * 输入：[0,0,null,0,0]
 * 输出：1
 * 解释：如图所示，一台摄像头足以监控所有节点。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-cameras
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: fengleifeng
 * @create: 2020-09-08 17:32
 **/
public class Num968监控二叉树 {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        /**
         * 思路：判断状态
         * 有三个状态:
         * 0=>这个结点待覆盖
         * 1=>这个结点已经覆盖
         * 2=>这个结点上安装了相机
         */
        public int minCameraCover(TreeNode root) {
            if (null == root) {
                return 0;
            }
            int now = dfs(root);
            if (now == 0) {
                res++;
            }
            return res;
        }

        int res = 0;

        public int dfs(TreeNode now) {
            if (now == null) {
                return 1;
            }
            int left = dfs(now.left);
            int right = dfs(now.right);
            if (left == 0 || right == 0) {
                res++;
                return 2;
            }
            if (left == 1 && right == 1) {
                return 0;
            }
            if (left + right >= 3) {
                return 1;
            }
            return -1;
        }
    }
}
